package com.wujunshen.algorithm.leetcode.basic;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/25 10:57<br>
 */
public class 等式方程的可满足性 {
  public static boolean equationsPossible(String[] equations) {
    int[] parent = new int[26];
    for (int i = 0; i < 26; i++) {
      parent[i] = i;
    }
    for (String str : equations) {
      if (str.charAt(1) == '=') {
        int index1 = str.charAt(0) - 'a';
        int index2 = str.charAt(3) - 'a';
        union(parent, index1, index2);
      }
    }

    for (String str : equations) {
      if (str.charAt(1) == '!') {
        int index1 = str.charAt(0) - 'a';
        int index2 = str.charAt(3) - 'a';
        if (find(parent, index1) == find(parent, index2)) {
          return false;
        }
      }
    }
    return true;
  }

  public static void union(int[] parent, int index1, int index2) {
    parent[find(parent, index1)] = find(parent, index2);
  }

  public static int find(int[] parent, int index) {
    while (parent[index] != index) {
      parent[index] = parent[parent[index]];
      index = parent[index];
    }
    return index;
  }

  public static void main(String[] args) {
    String[] x = {"a==b", "b==c", "a==c"};

    boolean result = equationsPossible(x);
    System.out.println(result);
  }
}
